1. Field of the Invention
The present invention relates to a data processing apparatus and data processing method, and to a recording medium, and particularly relates to a data processing apparatus and data processing method and recording medium enabling data embedding with high decoding precision, for example.
2. Description of the Related Art
FIG. 1 illustrates the configuration of an example of a conventional embedded coding apparatus which embeds data in pixels (pixel values) configuring an image, by performing bit-swapping, wherein bits making up bit strings representing pixels are swapped.
Art relating to bit-swapping has already been filed with the United States Patent and Trademark Office (USPTO) on Jun. 6, 2000, by the present Assignee, as Ser. No. 09/587,838.
Image data is supplied to image data memory 1, and the image data memory 1 temporarily stores the image data supplied thereto. Also, data to be embedded in the image data (hereafter also referred to as xe2x80x9cembedding dataxe2x80x9d) is supplied to embedding data memory 2, and the embedding data memory 2 temporarily stores the data to be embedded, supplied thereto.
A bit-swap embedding unit 3 sequentially, e.g., in raster scan order, takes pixels making up the image data stored in the image data memory 1, as pixels of interest, and reads out the pixel value thereof, and also reads out the data to be embedded which is stored in the embedding data memory 2. Further, the bit-swap embedding unit 3 performs bit-swapping of the bits making up the bit string representing the pixel value of the pixel of interest according to the data to be embedded, thereby embedding the data to be embedded in the pixel value of the pixel of interest, and supplies the pixel value obtained as the result of the embedding (hereafter also referred to as xe2x80x9cpost-embedding pixel valuexe2x80x9d) to post-embedding image data memory 4.
The post-embedding image data memory 4 stores the post-embedding pixel value supplied from the bit-swap embedding unit 3 at an address corresponding to the position of the pixel of interest, and in the event that post-embedding pixel values for one frame are stored, for example, outputs image data made up of the one frame of post-embedding pixel values (hereafter also referred to as xe2x80x9cpost-embedding image dataxe2x80x9d).
Next, the processing of the embedding coding apparatus (embedding coding processing) shown in FIG. 1 will be described with reference to the flowchart shown in FIG. 2.
In the event that the embedding coding apparatus is provided with, for example, one frame (or field) of image data and data to be embedded in that one frame of image data, the image data memory 1 stores the image data and the embedding data memory 2 stores the data to be embedded in step S1.
The flow then proceeds to step S2, where, in raster scan order, the bit-swap embedding unit 3 takes, of the pixels making up the image data stored in the image data memory 1, as pixel of interest, pixels that have not yet been made pixel of interest. The bit-swap embedding unit 3 reads out the pixel value thereof, and also reads out the data to be embedded from the embedding data memory 2, of an amount equivalent to the number of bits which can be embedded in the pixel value. Further, in step S2, the bit-swap embedding unit 3 performs bit-swapping of the bits making up the bit string representing the pixel value of the pixel of interest, according to the data to be embedded, thereby embedding the data to be embedded in the pixel value of the pixel of interest, and supplies the post-embedding pixel value obtained as a result of this embedding to the post-embedding image data memory 4, where it is stored.
Subsequently, the flow proceeds to step S3, the bit-swap embedding unit 3 judges whether or not all pixels making up the image data stored in the image data memory 1 have been subjected to processing as pixel of interest, and in the event that judgment is made that not all pixels have been processed as pixel of interest, the flow returns to step S2.
Also, in step S3, in the event that that judgment is made that all pixels making up the image data stored in the image data memory 1 have been processed as pixel of interest, i.e., in the event that the image data made up of the post-embedding pixel values for one frame (post-embedding image data) has been stored in the post-embedding image data memory 4, the flow proceeds to step S4, and the post-embedding image data memory 4 outputs the post-embedding image data stored therein, thereby ending the processing thereof.
The processing of the flowchart shown in FIG. 2 is preformed for one frame of image data each time one frame of image data is supplied to the embedded coding apparatus.
According to such embedded coding processing, data to be embedded is embedded in pixel values, as shown in FIG. 3, for example.
That is, FIG. 3 illustrates a case wherein the pixel value of the pixel of interest is 16, and data to be embedded with a value of 3 is to be embedded in the pixel of interest.
For example, saying that 8 bits are appropriated to the pixel value (the same holding true for the following description as well), the pixel value xe2x80x9c16xe2x80x9d, is generally represented as xe2x80x9c00010000xe2x80x9d in binary code. Accordingly, the bit string obtained by bit-swapping the binary code xe2x80x9c00010000xe2x80x9d can only be one of the eight patterns shown in FIG. 3. With regard to the bit strings making up the binary code corresponding to the pixel value, the bit-swap embedding unit 3 correlates and stores the swapping pattern of the bits making up the bit string (the bit-swap pattern) with the data to be embedded, and the binary code representing the pixel value of the pixel of interest is subjected to bit-swapping according to the pattern correlated with the embedding data which is to be embedded in the pixel of interest.
In FIG. 3, the eight bit-swap patterns obtained by performing bit-swapping of the binary code xe2x80x9c00010000xe2x80x9d representing the pixel value xe2x80x9c16xe2x80x9d, i.e., xe2x80x9c00010000xe2x80x9d, xe2x80x9c00100000xe2x80x9d, xe2x80x9c01000000xe2x80x9d, xe2x80x9c10000000xe2x80x9d, xe2x80x9c00000001xe2x80x9d, xe2x80x9c00000010xe2x80x9d, xe2x80x9c00000100xe2x80x9d, and xe2x80x9c00001000xe2x80x9d, are each correlated with the data to be embedded xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d, xe2x80x9c3xe2x80x9d, xe2x80x9c4xe2x80x9d, xe2x80x9c5xe2x80x9d, xe2x80x9c6xe2x80x9d, and xe2x80x9c7xe2x80x9d, and accordingly, in the event that the data to be embedded is xe2x80x9c3xe2x80x9d, the bit-swap embedding unit 3 performs bit-swapping of the binary code xe2x80x9c00010000xe2x80x9d representing the pixel value xe2x80x9c16xe2x80x9d with the binary code xe2x80x9c10000000xe2x80x9d correlated with xe2x80x9c3xe2x80x9d, and the pixel value xe2x80x9c128xe2x80x9d represented by the binary code xe2x80x9c10000000xe2x80x9d as the result of bit-swapping is output as the post-embedding pixel value.
According to the above, in the event of embedding data to be embedded in a pixel value by bit-swapping, how much data to be embedded that can be embedded in a pixel value is governed by the number of 0s or 1s in the bit string making up the binary code representing the pixel value.
That is to say, the amount of information which can be embedded in the pixel value is governed by the total number of bit-swap patterns of the binary code representing the pixel value, and with the total number of bit-swap patterns represented by N, the amount of information which can be embedded in the pixel value is log2 N bits. Now, FIG. 4 illustrates the relation between the number of 0s or 1s and the amount of information which can be embedded, with regard to 8-bit binary code.
Next, FIG. 5 illustrates the configuration of an example of a decoding apparatus for decoding the original pixel value and embedded data, from the post-embedding image data which is output from the embedded coding apparatus shown in FIG. 1.
The post-embedding image data is supplied to post-embedding image data memory 11, and the post-embedding image data memory 11 temporarily stores the post-embedding image data supplied thereto.
A bit-swap reverting unit 12 sequentially, e.g., in raster scan order, takes pixels making up the post-embedding image data stored in the post-embedding image data memory 11, as pixels of interest, reads out the post-embedding pixel value of the pixel of interest from the post-embedding image data memory 11, and also obtains a prediction value for the pixel value of the pixel of interest from a prediction value obtaining unit 15. Further, the bit-swap reverting unit 12 performs bit-swapping of the bits making of the bit string representing the post-embedding image value of the pixel of interest according to the prediction value of the pixel of interest, thereby decoding the pixel value of the pixel of interest, and also decoding the embedded data that was embedded in the pixel of interest. Note that the pixel value of the pixel of interest that has been decoded is supplied from the bit-swap reverting unit 12 to image data memory 13, and the embedding data is supplied from the bit-swap reverting unit 12 to embedded data memory 14.
Image data memory 13 temporarily stores the pixel value of the decoded pixel of interest supplied from the bit-swap reverting unit 12 at the address corresponding to the position of the pixel of interest. The embedded data memory 14 temporarily stores the decoded embedded data supplied from the bit-swap reverting unit 12.
The prediction value obtaining unit 15 obtains the prediction value of the pixel of interest based on the already-decoded pixel values stored in the image data memory 13, and supplies this to the bit-swap reverting unit 12.
Note that with the prediction value obtaining unit 15, of the already-decoded pixel values stored in the image data memory 13 for example, the pixel values adjacent to the pixel of interest above or to the left thereof, can be used without change as a prediction value. Or, with the prediction value obtaining unit 15, of the already-decoded pixel values stored in the image data memory 13 for example, an average value of the pixel values of the pixels positioned close to the pixel of interest either spatially or time-wise can be obtained that this average value used as the prediction value.
Next, the processing of the decoding apparatus shown in FIG. 5 (decoding processing) will be described with reference to the flowchart shown in FIG. 6.
In the event that, for example, one frame (or field) of post-embedding image data is supplied to the decoding apparatus, the post-embedding image data memory 11 stores the post-embedding image data in step s11.
Subsequently, the bit-swap reverting unit 12 sequentially, e.g., in raster scan order, takes, of the pixels making up the post-embedding image data stored in the post-embedding image data memory 11, as pixel of interest, pixels that have not yet been made pixel of interest. In step S12, the prediction value obtaining unit 15 obtains the prediction value of the pixel of interest based on already-decoded pixel values stored in the image data memory 13, and supplies the prediction value to the bit-swap reverting unit 12.
The bit-swap reverting unit 12 reads out the post-embedding pixel value of the pixel of interest from the post-embedding image data memory 11, receives the prediction value of the pixel value of the pixel of interest from the prediction value obtaining unit 15, and in step S13, decodes the pixel value of the pixel of interest by performing bit-swapping of the bits making up the bit string representing the post-embedding pixel value of the pixel of interest according to the prediction value of the pixel of interest, and also decodes the embedded data that was embedded in the pixel of interest, and the flow proceeds to step S14.
In step S14, the bit-swap reverting unit 12 supplies the decoded value of the pixel value of the pixel of interest to the image data memory 13 where it is stored, and also supplies the decoded value of the embedded data to the embedded data memory 14 where it is stored, and the flow proceeds to step S15.
In step S15, the bit-swap reverting unit 12 judges whether or not all pixels making up the post-embedding image data stored in the post-embedding image data memory 11 have been subjected to processing as pixel of interest, and in the event that judgment is made that not all pixels have been processed as pixel of interest, the flow returns to step S12, with a pixel that has not yet been made a pixel of interest as a new pixel of interest, in raster scan order.
Also, in step S15, in the event that that judgment is made that all pixels making up the post-embedding image data stored in the post-embedding image data memory 11 have been processed as pixel of interest, i.e., in the event that the one frame of pixel values making up the image data is stored in the image data memory 13, and also one frame of pixel values making up the embedded data embedded in the image data is stored the embedded data memory 14, the flow proceeds to step S16, the image data (or rather the decoded value thereof) stored in the image data memory 13 is output therefrom, while the embedded data (or rather the decoded value thereof) stored in the embedded data memory 14 is output therefrom, and the processing ends.
Note that the processing of the flowchart shown in FIG. 6 is preformed for one frame of post-embedding image data each time one frame of post-embedding image data is supplied to the decoding apparatus.
According to such decoding processing, the post-embedding pixel values are decoded into pixel values and embedded data, as shown in FIG. 7, for example.
That is, as described with reference to FIG. 3, FIG. 7 illustrates a case of decoding the post-embedding pixel value xe2x80x9c128xe2x80x9d obtained by embedding data to be embedded with a value of xe2x80x9c3xe2x80x9d into a pixel value of xe2x80x9c16xe2x80x9d.
The binary code representing the post-embedding pixel value xe2x80x9c128xe2x80x9d is xe2x80x9c10000000xe2x80x9d, and this binary code is obtained by performing bit-swapping on the binary code representing the original pixel value, so the binary code representing the original pixel value exists with the all of the bit string patterns obtained by performing bit-swapping on the binary code xe2x80x9c10000000xe2x80x9d representing the post-embedding pixel value xe2x80x9c128xe2x80x9d. Accordingly finding the binary code representing the original pixel value from the all of the bit string patterns obtained by performing bit-swapping on the binary code xe2x80x9c10000000xe2x80x9drepresenting the post-embedding pixel value xe2x80x9c128xe2x80x9d decodes the original pixel value.
Also, the binary code corresponding to the original pixel value is made to be a post-embedding pixel value by performing bit-swapping according to the bit-swap pattern corresponding to the data to be embedded, so once the bit-swap pattern for making the binary code representing the post-embedding pixel value into the binary code representing the original pixel value is found, the embedded data embedded in the post-embedding pixel value can be decoded.
Thus, in order to decode the pixel value, the bit-swap reverting unit 12 first performs bit-swapping of the binary code xe2x80x9c10000000xe2x80x9d representing the post-embedding pixel value xe2x80x9c128xe2x80x9d, thereby obtaining bit strings of all patterns obtained from that binary code. Further, the bit-swap reverting unit 12 finds the bit string of a pattern wherein the prediction margin of error of the prediction value of for the pixel of interest from the prediction value obtaining unit is smallest as to the pixel value indicated by each bit string pattern. That is to say, in the event that the prediction value for the pixel of interest output by the prediction value obtaining unit 15 is xe2x80x9c14xe2x80x9d, of the pixel values represented by the eight bit string patterns shown in FIG. 7 obtained from the binary code xe2x80x9c10000000xe2x80x9d representing the post-embedding pixel value xe2x80x9c128xe2x80x9d, that with the smallest prediction margin of error with the prediction value xe2x80x9c14xe2x80x9d is xe2x80x9c16xe2x80x9d, so this pixel value xe2x80x9c16xe2x80x9d is decoded as the original pixel value.
Also, the bit-swap reverting unit 12 stores correlating information for correlating the bit-swap-pattern and embedded data which is the same as with the bit-swap embedding unit 3, and based on this correlating information, decodes the embedded data xe2x80x9c3xe2x80x9d correlated to the bit-swap pattern for bit-swapping the binary code xe2x80x9c0000100xe2x80x9d representing the decoded pixel value xe2x80x9c16xe2x80x9d into the binary code xe2x80x9c10000000xe2x80x9d representing the post-embedding pixel value xe2x80x9c128xe2x80x9d as the embedded data embedded in the pixel value xe2x80x9c16xe2x80x9d of the pixel of interest.
Thus, the post-embedding pixel value xe2x80x9c128xe2x80x9d is decoded as the original pixel value xe2x80x9c16xe2x80x9d and the embedded data xe2x80x9c3xe2x80x9d embedded therein.
Now, in the event that the post-embedding image data is being decoding in raster scan order for example, and the pixel value of the pixel adjacent to the pixel of interest to the left is used without change as the prediction value of the pixel of interests, this means that there is no pixel value existing as a prediction value of the pixels at the far left of the post-embedding image data. Accordingly, an arrangement may be employed wherein, for example, no data to be embedded is embedded in pixels at the far left of the post-embedding image data at the time of coding, and also the pixels to the right of the pixels at the far left of the post-embedding image data become the object of decoding at the time of decoding.
Now, the decoding apparatus shown in FIG. 5 performs decoding of the pixel value and embedded data, presupposing that the prediction margin of error of the prediction value of the pixel value of the pixel of interest is small.
Accordingly, as described with reference to FIG. 7, in the event that a prediction value xe2x80x9c14xe2x80x9d relatively precisely predicting the original pixel value xe2x80x9c16xe2x80x9d is obtained in the case of decoding the post-embedding pixel value xe2x80x9c128xe2x80x9d obtained by embedding data with a value of xe2x80x9c3xe2x80x9d in a pixel value xe2x80x9c16xe2x80x9d, the post-embedding pixel value xe2x80x9c128xe2x80x9d can be accurately decoded to the original pixel value xe2x80x9c16xe2x80x9d.
However, even in cases wherein the prediction value precision is relatively good, it may be difficult to accurately decode the post-embedding pixel value into the original pixel value if the original pixel value is small. Further, with the decoding apparatus shown in FIG. 5, the embedded data decoded based on the bit-swap pattern with which the binary code indicating the original pixel value is bit-swapped into the binary code representing the post-embedding pixel value cannot be accurately decoded, unless the pixel value can be accurately decoded.
Specifically, in the event that the pixel value of the pixel of interest is small, let us say, xe2x80x9c2xe2x80x9d, this cannot be accurately decoded even if a relatively accurate xe2x80x9c1xe2x80x9d is obtained as the prediction value for the pixel of interest.
That is to say, the binary code for the pixel value of the pixel of interest xe2x80x9c2xe2x80x9d is xe2x80x9c00000010xe2x80x9d, so there are eight patterns for the bit-swap pattern of this binary code as with the case shown in FIG. 7, and the embedded encoding makes a post-embedding pixel value representing one of the bit strings of the eight patterns. Then, at the time of decoding the post-embedding pixel value, even in the event that the xe2x80x9c1xe2x80x9d is obtained as the prediction value with a relatively high prediction precision (a prediction value close to the original pixel value xe2x80x9c2xe2x80x9d) is obtained as described above, the bit string of the eight patterns with only one bit of xe2x80x9c1xe2x80x9d shown in FIG. 7 which makes the prediction margin of error of the prediction value xe2x80x9c1xe2x80x9d smallest is the binary code representing xe2x80x9c00000001xe2x80x9d xe2x80x9c1xe2x80x9d, so the post-embedding pixel value xe2x80x9c2xe2x80x9d is decoded to the pixel value xe2x80x9c1xe2x80x9d represented by the binary code xe2x80x9c00000001xe2x80x9d, and is not decoded to the original pixel value xe2x80x9c2xe2x80x9d.
Thus, the state wherein pixel values with small values cannot be accurately decoded even in the event that a relatively accurate prediction value is obtained, is due to the binary code appropriated to the pixel values.
That is, considering the 8-bit binary codes wherein there is, for example, only one bit of xe2x80x9c1xe2x80x9d (and thus 7 bits of xe2x80x9c0xe2x80x9d), there are eight bit-swap patterns for such binary code as shown in FIG. 7, but the pixel values which the eight patterns of binary code, xe2x80x9c00000001xe2x80x9d, xe2x80x9c00000010xe2x80x9d, xe2x80x9c00000100xe2x80x9d, xe2x80x9c00001000xe2x80x9d, xe2x80x9c00010000xe2x80x9d, xe2x80x9c00100000xe2x80x9d, xe2x80x9c01000000xe2x80x9d, and xe2x80x9c10000000xe2x80x9d, represent, are xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d, xe2x80x9c14xe2x80x9d, xe2x80x9c8xe2x80x9d1, xe2x80x9c116xe2x80x9d, 1xe2x80x9c32xe2x80x9d, xe2x80x9c64xe2x80x9d, and xe2x80x9c128xe2x80x9d. The intervals between the pixel values corresponding to these eight patterns of binary code are fine at some places and coarse at others. In other words, the intervals between pixel values are great at portions where the pixel value is great, and the intervals between pixel values are small at portions where the pixel value is small.
Accordingly, with regard to pixel values which have fine intervals, such as xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d, xe2x80x9c4xe2x80x9d, and so forth, even in the event that a prediction value is obtained with relatively high precision, the prediction value of that pixel value is makes the prediction margin of error as to other pixel values near that pixel value to be the smallest, and often does not make the prediction margin of error as to the true pixel value to be the smallest. Consequently, the pixel value is not accurately decoded, as described above.
The present invention has been made in light of the above problems, and accordingly, it is an object of the present invention to enable data embedding with high decoding accuracy.
According to a first aspect of the present invention, a data processing apparatus for embedding second digital data in first digital data comprises: bit-swap means for bit-swapping target data comprising a predetermined number of bits within the first digital data; predicting means for outputting a prediction value which predicts a value corresponding to the target data from marginal data surrounding the target data; sorting means for sorting target data subjected to the bit-swapping according to the prediction margin of error value between a prediction value output by the predicting means and respective values corresponding to target data subjected to the bit-swapping; correction code output means for outputting correction code according to target data subjected to the bit-swapping that has been sorted by the sorting means; and embedded data output means for outputting, as embedded data, one of the target data subjected to the bit-swapping that has been sorted by the sorting means, according to the second digital data.
Also, according to another aspect of the present invention, a decoding apparatus for decoding first digital data and second digital data from embedded data wherein the second digital data is embedded in the first digital data and from a correction code, comprises: bit-swap means for bit-swapping target data comprising a predetermined number of bits within the embedded data; predicting means for outputting a prediction value which predicts a value of decoded data decoded from the target data, from a value corresponding to decoded data surrounding the target data which has already been decoded; sorting means for sorting target data subjected to the bit-swapping according to the prediction margin of error value between a prediction value output by the predicting means and respective values corresponding to target data subjected to the bit-swapping by the bit-swap means; decoded data output means for outputting, as decoded data, one code of the bit-swapped target data sorted by the sorting means, according to the correction code; and second digital data output means for outputting second digital data according to the order of the target data, by bit-swapped target data sorted by the sorting means.
Thus, according to the present invention, a first code which is a bit string appropriated to the values of first data is converted into second code which is a bit string appropriated to the values such that the intervals between values corresponding to a bit string with the same number of 0s and 1s are uniform and coarse, and also the prediction value of first data of interest which is a first data of interest, is obtained. Performing bit-swapping wherein the bits of the second code corresponding to the first data of interest are swapped, based on the second data and the prediction value of the first data of interest, embeds the second data in the first data of interest. Accordingly data embedding can be performed with high decoding accuracy.
Also, according to the present invention, of embedded data represented by second code which is a bit string appropriated to values such that the intervals between values corresponding to a bit string with the same number of 0s and 1s is uniform, this second code having been converted from a first code which is a bit string appropriated to the values of first data, the prediction value of first data of interest which is a first data of interest, corresponding to the embedded data of interest, is obtained. Further, performing bit-swapping wherein the bits of the second code corresponding to the embedded data are swapped, based on the prediction value of the first data of interest, decodes the first data of interest represented by the second code, and also decodes the second data embedded in this first data of interest, Then, the second code representing the first data of interest is converted into first code. Accordingly, the data can be decoded with high accuracy.